Most morphological operations can be defined in terms of two fundamental image-processing operations, dilation and erosion. As their names imply, the dilation operation expands image features, while the erosion operation contracts them. These conventional operations are described below in connection with FIGS. 1A and 1B; for a detailed explanation of conventional dilation and erosion, see pp. 518-560 of Gonzales and Wood, "Digital Image Processing," Addison-Wesley 1992), which is incorporated herein by reference.
FIG. 1A depicts an image 100, which includes a plurality of random pixels 110, and a structuring element 120 of radius r. The dilation of image 100 by structuring element 120 is conventionally accomplished by superimposing the origin (e.g., the center) of element 120 sequentially over each of pixels 110. The dilation operation then selects each image pixel covered by element 120. Whether element 120 covers a given image pixel is determined by comparing the location of that image pixel with the locations of the pixels defined within element 120. FIG. 1B depicts image 100 after dilation using element 120. Each of pixels 110 is shown included within a disk 130 of selected image pixels. Each disk 130 has a radius equal to the radius of element 120. overlapping groups of disks 130 create a pair of objects 140 and 150.
FIG. 2A depicts objects 140 and 150 and the isolated disk 130, all of FIG. 1B, undergoing a conventional erosion process. A structuring element 200 of radius .di-elect cons. is provided for the erosion. The erosion of objects 140 and 150 and the isolated disk 130 by structuring element 200 is conventionally accomplished by superimposing the origin (e.g., the center) of element 200 over each object pixel of image 100. The only pixels selected by the erosion process are those at which structuring element 200, when centered on the pixel, lies completely within one of object 140, object 150, or the isolated disk 130. Whether element 200 lies completely within one of object 140, object 150, or the isolated disk 130 is determined by comparing the location of each pixel of element 200 with the locations of corresponding pixels of image 100. The results of such erosion are illustrated in FIG. 2B as objects 210, 220, 230, and 240.
The trouble with conventional dilation and erosion techniques is that they are relatively computation intensive. For an image of n pixels, either dilation or erosion requires on the order of n.sup.3 individual pixel comparisons. There is therefore a need for faster methods of image dilation and erosion.